package com.wuyou.dataStructure.tree;

/**
 * 构建二叉树
 * 从中序与后序遍历序列构造二叉树
 */
public class BuildTree {


    /**
     * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
     * 输出：[3,9,20,null,null,15,7]
     * 中序：左-根-右
     * 后续：左-右-根
     * 后序遍历的数组，最后的节点是根节点，根节点在中序遍历的数组里面，左边是左子树、右边是右子树
     * @param inorder   中序遍历二叉树
     * @param postorder 后序遍历二叉树
     * @return
     */
    public TreeNode sol_2(int[] inorder, int[] postorder) {
        int len = inorder.length;
        if(len==0) return null;
        // 1、找到根节点
        // 2、区分左右子树

        return null;
    }

    /**
     * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
     * 输出：[3,9,20,null,null,15,7]
     *
     * @param inorder   中序遍历二叉树
     * @param postorder 后序遍历二叉树
     * @return
     */
    public TreeNode sol_1(int[] inorder, int[] postorder) {
        int len = inorder.length;
        if(len==0) return null;

        return dfs(inorder, postorder, 0, len-1, 0, len - 1);
    }

    public TreeNode dfs(int[] inorder, int[] postorder, int head1, int tail1, int head2, int tail2){
        if(head2 > tail2){return null;}

        int val=postorder[tail2];
        TreeNode root = new TreeNode(val);
        if(head2==tail2) return root;
        int mid =0;
        while(inorder[head1+mid]!=val)mid++;
        root.left = dfs(inorder, postorder, head1, head1+mid-1, head2, head2+mid-1);
        root.right = dfs(inorder, postorder, head1+mid+1, tail1, head2+mid, tail2-1);
        return root;
    }
}
